package NC2_重排链表;


class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class Solution {
    public void reorderList(ListNode head) {
        if (head == null || head.next == null){
            return;
        }
        // 快慢指针找到中点
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }

        // 拆分链表，反转中间结点之后的链表
         ListNode second = reverse(slow.next);

        // 合并两个链表
        merge(head, second);

    }

    private void merge(ListNode first, ListNode second) {
        ListNode fNext = first.next;
        ListNode sNext = second.next;

        while (first != null){
            first.next = second;
            second.next = fNext;
            first = fNext;
            second = sNext;

            if (sNext != null) {
                fNext = fNext.next;
                sNext = sNext.next;
            } else {
                first.next = null;
                break;
            }
        }
    }

    private ListNode reverse(ListNode head) {
        ListNode pre = null;
        while (head != null){
           ListNode last = head.next;
           head.next = pre;
           pre = head;
           head = last;
        }
        return pre;
    }
}